RS encoding and decoding can be defined as constituting a polynomial using the element in the Galois field GF(2m). The following codeword polynomial W(x) is calculated for (n, k) RS encoding where n denotes the number of code blocks and k denotes the number of information blocks (a test block is nxe2x88x92k=2t, where t is the maximum correctable number of symbols).
W(x)=M(x)xnxe2x88x92kxe2x88x92R(x)
where
M(x): a polynomial using information symbols as coefficients;
R(x): a polynomial using parity symbols as coefficients;
R(x)=M(x)xnxe2x88x92k mod G(x); and
G(x): generator polynomial,
G(x)=(xxe2x88x92ad)(xxe2x88x92adxe2x88x921) . . . (xxe2x88x92ad+2txe2x88x921).
In the above equation, a is defined by GF(2m) and is a solution of the m-order irreducible polynomial, i.e., a solution that satisfies a8+a4+a3+a2+1=0 when m=8. The polynomial W(x) can be divided by G(x) without yielding a remainder. The codeword polynomial W(x) can be a systematic codeword, compared with a method that calls for the direct multiplication of M(x) by G(x).
Generally, an LFSR (Linear Feedback Shift Register) is used for calculating the remainder of the M(x)xnxe2x88x92k by G(x). If one LFSR is used for the encoding one block, the LFSR has 2t constant multipliers and uses them (nxe2x88x922t) times. Thus, 2(nxe2x88x922t)t constant multiplications must be performed for the encoding.
The RS decoding is an operation used for estimating the original W(x) by using a received polynomial
Y(x)=W(x)+E(x).
E(x) is a polynomial using an error symbol as a coefficient. Y(x) can also be expressed as follows, where Yi is a received codeword,
xe2x80x83Y(x)=Ynxe2x88x921xnxe2x88x921+Ynxe2x88x922xnxe2x88x922+ . . . Y1x+Y0.
The decoding methods are mainly
(i) a method for using Y(x) to perform decoding in a time domain;
(ii) a method for using for a polynomial a remainder obtained by dividing Y(x) by G(x) (remainder-based decoding); and
(iii) a method for performing a DFT (Discrete Fourier Transformation) for Y(x) to calculate 2t continuous spectra (syndromes) in a frequency domain (syndrome-based decoding).
According to the second and the third methods, information that depends only on an error (i.e. syndromes) is calculated by using the received information, and the location of the error is extracted. Thus, the number of terms is not O(n), but instead is reduced to O(t). Therefore, since generally t less than n, a required circuit in the succeeding stages is small. The third method (iii) is generally used, and is further sorted into algebraic decoding and transform decoding. The prior art will now be described by using the two decoding methods that are most closely related to the present invention.
(a) Algebraic Decoding
Specifically, this method includes the following five steps that must be performed for decoding:
(i) calculating a syndrome by performing a DFT for a received codeword;
(ii) obtaining an error-locator polynomial and an error-evaluator polynomial by using the calculated syndrome;
(iii) calculating the solution for the error-locator polynomial in order to estimate the location of the error;
(iv) estimating an error value from the error-locator and the error-evaluator polynomial by using the Forney algorithm; and
(v) correcting the error by using the received codeword and the error value.
In the calculation of the syndrome at step (i), the DFT calculation for GF(2m) need be performed. The DFT calculation is performed by substituting into Y(x) the elements 1, a, a2, a3 . . . and a2txe2x88x921 of GF(2m). That is, the syndrome is obtained by
S0=Y(1)
S1=Y(a)
S2=Y(a2)
S3=Y(a3)
.
.
.
S2txe2x88x921=Y(a2txe2x88x921).
Since W(ai)=0,
Si=Y(ai)=W(ai)+E(ai)=E(ai)(i=0, . . . , 2txe2x88x921).
The occurrence of an error in Y(x) can be determined by examining the syndromes to determine whether they are all 0. Since generally 2t arithmetic circuits are used n times to calculate the syndromes, 2nt constant multiplications are required.
Error correction using the syndromes is performed by estimating the number of errors using Si. This is the calculation performed with E(x) that provides the calculated syndrome and that has a Hamming weight of t or less (i.e., that includes non zero terms equal to or less than t), and is the NP complete problem in general. However, the calculation method in the polynomial order is well known for RS code. At step (ii) the coefficient for the following error-locator polynomial is calculated by using the fact that the syndromes can be expressed as a linear combination of error values, and that symmetry exists relative to the exchange of orders of error locations.
Expression 1      Λ    ⁢          (      x      )        =            ∏              k        =        0                    t        -        1              ⁢          (              1        +                              a                          i              k                                ⁢          x                    )      
Coefficients xcex9t . . . and xcex9l for xcex9(x) are obtained by the following expression, wherein L0 is defined as 1.
Expression 2            [                                                  S              0                                                          S              1                                            …                                              S                              t                -                1                                                                                        S              1                                                          S              2                                            …                                              S              t                                                            ⋮                                ⋮                                              xe2x80x83                                            ⋮                                                              S                              t                -                1                                                                        S                              t                -                2                                                          …                                              S                                                2                  ⁢                  t                                -                2                                                        ]        ⁡          [                                                  Λ              t                                                                          Λ                              t                -                1                                                                          ⋮                                                              Λ              1                                          ]        =      [                                        S            t                                                            S                          t              +              1                                                            ⋮                                                  S                                          2                ⁢                t                            -              1                                            ]  
The Peterson method, the Berlekamp-Massey (BM) method and the Euclid method are proposed for performing this calculation in the polynomial order. According to these methods, O(t3), O(t2) and O(t2) multiplications are respectively performed to calculate the coefficients of the error-locator polynomial. Since these calculations are not directly related to the subject of the present invention, however, no further explanation shall be given for them. For the details, see the referenced document 1, xe2x80x9cTheory And Practice Of Error Control Codes,xe2x80x9d R. E. Blahut, Addison-Wesley 1984, or referenced document 2, xe2x80x9cCoding Theory,xe2x80x9d Hideki Imai, Institute of Electronic Information Communication, 1990.
When the coefficients xcex9t . . . and xcex9l of the error-locator polynomial are obtained, at step (iii) an error location i is obtained by performing the calculations for the polynomial. Generally, axe2x88x92i (i=0, 1, . . . , nxe2x88x921) are sequentially substituted into the error-locator polynomial, and the relation xcex9(axe2x88x92i)=0 is checked by using a sequential circuit (Chien Search). Since xcex9(x) is the t-order polynomial, t constant multiplications must be repeated n times (a total of nt constant multiplications).
At step (iv), the Forney algorithm is used to calculate the error value by employing the following error-evaluator polynomial
xcexa9(x)=S(x)xcex9(x) mod x2txe2x88x921,
where S(x) is the following polynomial having syndromes as coefficients:
Expression 3      S    ⁢          (      x      )        =            ∑              i        =        0                              2          ⁢          t                -        1              ⁢                  S        i            ⁢              x        i            
The obtained error value Ei is
Ei=xcexa9(axe2x88x92i)/(xcex9xe2x80x2(axe2x88x92i)axe2x88x92i),
where xcex9xe2x80x2(x) represents the derivative of xcex9(x).
Finally, at step (v) the error is corrected. That is,
W(x)=Y(x)+E(x)
Most of these calculations are performed as sequential steps using a sequential circuit, as previously mentioned. Specifically, steps (i) to (v) are sequentially performed, and at each step many processes are sequentially performed, including iterative calculations. The implementation of the RS decoder does not precipitate any problem in applications that has a relatively low data transfer rate. However, with a memory ECC application for which high through-put and low latency are required, a problem may arise concerning the processing speed.
The RS decoder requires only the linear calculation performed up to the acquisition of syndromes (step (i)), but for the following process to estimate the error location and error value, it requires multiple non-linear circuits. It is difficult to provide a small, fast circuit for the nonlinear calculation in the Galois field (a circuit for two-input multiplication, reciprocal calculation, etc.) using the basic logical function primitives (AND and XOR).
To resolve the problem concerning the processing speed, a combinational circuit can be provided. Actually, in BCH encoding, the part of the circuit used for calculating the coefficients of a polynomial is developed into a combinational circuit. The calculation expressions up to t=5 are represented, and an example for t=3 is disclosed in U.S. Pat. No. 5,343,481 However, in the design of the combinational circuit, a circuit sharing which is one of the design techniques that are frequently used in the design of sequential circuits is difficult. Therefore, unless the processing flow is so designed that the number of nonlinear operations is reduced, the number of nonlinear operating units required is increased in accordance with the number of iterative steps performed in a loop, a number that is increased in proportion to t, and the number of conditional branches in the loop. In addition, while in the BCH code only the error locations need be obtained, in the RS code not only the error locations but also the error values must be obtained. As a result, when t greater than 1, the RS encoding uses more nonlinear operations than does the BCH encoding.
Because of the above described background, in most cases a conventional RS decoder is provided as a sequential circuit. In prior art, only when the maximum number of correctable symbols is small (t=1) the RS decoder is provided as a combinational circuit.
Specific problems will now be described that arise when algebraic decoding is implemented by using a combinational circuit.
(1) One problem arises when the Peterson method, the BM method or the Euclid method, which are frequently used to obtain the error-locator polynomial and the error-evaluator polynomial, are implemented as combinational circuits. Since the Peterson method provides a simple, direct method for the calculation of coefficients when the maximum number of correctable error symbol t is small (e.g., two), the Peterson method can be implemented by a combinational circuit. However, when the number of error symbols is increased, the size of the operations is increased as O(e3) when e is the actual number of error in the received codeword. Therefore, the Peterson method is implemented by using the combinational circuit, and circuits for the calculation of coefficient xcex9(x) must be prepared in a number equivalent to the error count, which is equal to or smaller than t, so that the size of the circuit is increased by the amount
Expression 4      ∑          e      =      1        t    ⁢            e      3        ~          O      ⁢              (                  t          4                )            
instead of O(t3). The BM method provides a calculation algorithm that requires only the calculation amount O(t2). However, since a plurality of conditional branches are included in a single loop, it is not easy to increase the processing speed by using the algorithm to implement the combinational circuit within a practical number of gate size. Especially for RS encoding, the number of required loops is double that required for BCH encoding (see referenced documents 1 and 2). While the Euclid method also requires only the calculation amount O(t2), it includes the division by a polynomial, so that the size of a combinational circuit required to implement this method is unrealistically large.
(2) If, for the estimation of an error value, following the Chien Search, paths are merely arranged in parallel to constitute a combinational circuit, n dividers have to be prepared for the Forney Algorithm for the calculation of the error value. In this case, not all the dividers are effectively used; actually, only the dividers equivalent in number to the error corrections t are actually used. In addition, even when the dividers are designed to be used in common, the size of the circuit is not reduced very much, whereas the decoding speed is lowered considerably. This occurs because a circuit for allocating dividers in accordance with the error location requires 2t n-bit multiplexers (t multiplexers each at the preceding and succeeding stages) and t priority encoders.
(b) Transform Decoding
In the present invention, for decoding. the following five steps are performed:
(i) calculation of syndromes by performing a DFT for received codeword;
(ii) calculation of coefficients for an error-locator polynomial by using the obtained syndromes;
(iii) reflexive calculation of the DFT elements of n errors without resolving the error-locator polynomial;
(iv) calculation of error values by performing an IDFT (Inverse DFT); and
(v) correction of the errors by using the received codeword and the error values.
The method in (a) is used for steps (i) and (ii). At step (iii) the DFT elements E*i of the errors are obtained. Since the following relationship is established for the first 2t,
E*i=E(ai)=Si(i=0, . . . , 2txe2x88x921),
the high-order elements are calculated using
Expression 5      E    i    *    =            ∑              j        =        1                    n        -        1              ⁢                  Λ        j            ⁢              E                  i          -          j                *            
where i=2t, . . . , nxe2x88x921.
At step (iv), an IDFT is performed by substituting axe2x88x92i (i=0, . . . nxe2x88x921) into the polynomial that is defined bv using E*i as a coefficient. That is,
Ei=E*(axe2x88x92il)
is used to calculate error value Ei.
The method described in (a) is performed at step (v).
Since a division circuit is not used for transform decoding, a problem precipitated by a division circuit, when method (a) is used to implement the combinational circuit, does not arise when method (b) is used. However, the following problems, in addition to the calculation of coefficient xcex9(x), which is one ofthe problems that accompany the implementation of method (a), are encountered with method (b).
(1) While the same circuit in the sequential circuit can be iteratively used to calculate all the values Ei, nxe2x88x922t circuits must be prepared for a combinational circuit. And since t 2-input multipliers are required for a single iteration, a total of t(nxe2x88x922t) 2-input multipliers are required. In addition, since a recursive calculation is performed, i.e., a low-order calculation must be completed before a next-order calculation is begun, the calculation speed cannot be increased very much by implementing a combinational circuit.
(2) Since the error values are calculated after all the DFT elements for n errors are obtained from the syndromes, this algorithm is easily implemented by a combinational circuit, but for an IDFT, an enormous number of circuits must be used. That is, for an IDFT n2 constant multipliers are required.
It is, therefore, one object of the present invention to provide a high-speed, low power consumption Reed-Solomon decoder.
It is another object of the present invention to constitute a Reed-Solomon decoder by using only a combinational circuit, and without using a sequential circuit.
It is an additional object of the present invention to provide a Reed-Solomon decoder having a circuit size that can actually be achieved.
To achieve the above objects, according to the present invention, a Reed-Solomon decoder that can correct t errors or fewer comprises: a syndrome calculation circuit for calculating syndromes Sj (j=0, 1, . . . , 2txe2x88x921) using the first codeword Yi (i=0, 1, . . . , nxe2x88x921) (so-called received codeword) that may include errors; a coefficient calculation circuit for, by using the syndromes Sj, calculating coefficients xcex9k (k=1, . . . , e) of an error-locator polynomial, the coefficients xcex9k corresponding in number to e estimated errors (exe2x89xa6t less than n), and for, by using the syndromes Sj, calculating coefficients Er1 (1=0, . . . , xc3xaa) (xc3xaa can be as small as O(e)) of an error polynomial, the coefficients Er1 corresponding in number to the e estimated errors; an error value calculation circuit for calculating error values Ei by using the coefficients Er1 of the error polynomial, and for using the coefficients xcex9k of the error-locator polynomial to generate a signal concerning the error value Ei to be used; and an output circuit for using the first codeword Yi and the error value Ei, which correspond to the signal used to calculate the second codeword Wi (so-called source codeword) in which the estimated errors are corrected. Since exe2x89xa6t less than n, and since there are e coefficients xcex9k and xc3xaa coefficients Er1, the number of calculations performed by, and the sizes of the coefficient calculation circuit and the error value calculation circuit are reduced. Specifically, since the coefficient circuit is required to perform a nonlinear operation in order to calculate the coefficients xcex9k and Er1, the effects achieved by such a reduction are greater.
At least one of the syndrome calculation circuit, the coefficient calculation circuit, the error value calculation circuit and the output circuit is constituted by a combinational circuit, as will be described later. And as a result, the calculation speed is increased.
The coefficient calculation circuit is so designed that it includes a circuit for calculating, in the ascending order of e coefficients xcex9w(e) (w=1, . . . , e) of an error-locator polynomial corresponding to the number e (exe2x89xa6t) of errors by using the syndromes Sj and coefficients xcex9v(nxe2x88x921) (v=1, . . . , exe2x88x921). By using this circuit in common, the size of the circuit can be limited.
The error value calculation circuit performs a calculation by using the element ai and the inverse element axe2x88x92i of the Galois field GF(2m) corresponding to an error location i. In this case, by using a linear operation the calculation can be performed at high speed.
The coefficient calculation circuit may further use the coefficients xcex9k ofthe error-locator polynomial, which correspond to the estimated errors e, in order to calculate the coefficients Er1 of the error polynomial corresponding to the estimated errors e.
When a value of 0 is obtained by substituting the inverse element axe2x88x92i of GF(2m) corresponding to the error location i, into the error-locator polynomial, the error value calculation circuit outputs a signal indicating the error values Ei are to be used. In the other cases, the error value calculation circuit outputs a signal indicating the error values Ei are not to be used.
The error value calculation circuit may include a constant multiplier for receiving the coefficients Er1 of the error polynomial, and a constant multiplier for receiving the coefficients xcex9k of the error-locator polynomial. When the element ad and the inverse element axe2x88x921 of the Galois field GF(2m) corresponding to the error location i are used, because the values are constants, the multipliers are hard-wired.
The thus arranged present invention can be applied for memory circuits for which high speed and low power consumption are demanded. These memory circuits are, for example, (i) a fast error correction circuit with low power consumption for extending the DRAM refresh time; (ii) a main memory redundancy circuit for a server for which high reliability and an adequate processing speed are desired; and (iii) a cache memory ECC circuit for which a high processing speed is desired.